package com.aikon.wht.paoshan.alg;

import java.util.Random;

/**
 * <pre>
 * 线性表数据结构包括数组，链表，栈，队列。线性表中的数据只有前后方向。
 * 数组
 *  数组是一种线性表数据结构，它用一组连续的空间存储一组类型相同的数据。便于随机读取，例如a[i]=base_addr + i*data_size，根据下标随机读取的时间复杂度为O(1)
 *
 * 链表
 *  包括单向链表，双向链表，循环链表，双向循环链表
 *
 * 栈
 *  一种操作受限的线性表，只允许一端插入或删除数据。先进后出。分为数组实现的顺序栈和链表实现的链式栈。
 *
 *      栈的应用：
 *      1.PaoshanOfKuoHao
 *      2.函数调用（函数调用之所以用栈，是因为函数调用中经常嵌套，栗子：A调用B，B又调用C，那么就需要先把C执行完，结果赋值给B中的临时变量，B的执行结果再赋值给A的临时变量，嵌套越深的函数越需要被先执行，这样刚好符合栈的特点，因此每次遇到函数调用，只需要压栈，最后依次从栈顶弹出依次执行即可）
 * 队列
 *  一种操作受限的线性表，只允许出队或入队。先进先出，分为数组实现的顺序队列和链表实现的链式队列。
 *      队列的应用：
 *      1.阻塞队列
 *      2.并发队列
 *
 * 衍生数据结构
 *  有序数组 - 适用于静态存储引擎，等值查询及范围查询都非常优秀(二分法 - O(logn))，插入则需要移动后面所有元素，成本太高
 *  跳表 - 可二分查找的多层索引有序链表，范围查找效率比红黑树高，插入，删除，查找时间复杂度都是O(logn)，空间复杂度O(n)
 *  散列表 - 散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
 *           适用于等值查询
 *           散列表解决散列冲突的方法：
 *           1.开放寻址法(散列表中的数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度，比起链表法来说，冲突的代价更高。适合数据量小，装载因子小的场景)
 *              ThreadLocalMap
 *           2.链表法(基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树，跳表代替链表。)
 *              HashMap(链表长度大于8时，链表转换为红黑树)
 *
 *
 * 非线性表包括二叉树，堆，图。非线性表中的数据不只有前后方向。
 *
 * 图
 *  广度优先 - bfs
 *  深度优先 - dfs
 *
 * 基本算法思想
 * 贪心
 * 分治
 * 回溯
 * 动态规划
 * </pre>
 *
 * @author WANGHAITAO273
 */
public class PaoshanOfAlgBase {


    /**
     * 数组队列
     */
    public class ArrayQueue {
        // 数组：items，数组大小：n
        private String[] items;
        private int n = 0;
        // head表示队头下标，tail表示队尾下标
        private int head = 0;
        private int tail = 0;

        // 申请一个大小为capacity的数组
        public ArrayQueue(int capacity) {
            items = new String[capacity];
            n = capacity;
        }

        // 入队
        public boolean enqueue(String item) {
            // 如果tail == n 表示队列已经满了
            if (tail == n) return false;
            items[tail] = item;
            ++tail;
            return true;
        }


        // 入队操作，将item放入队尾，并重复使用空间
        public boolean enqueueAndReuse(String item) {
            // tail == n表示队列末尾没有空间了
            if (tail == n) {
                // tail ==n && head==0，表示整个队列都占满了
                if (head == 0) return false;
                // 数据搬移
                for (int i = head; i < tail; ++i) {
                    items[i - head] = items[i];
                }
                // 搬移完之后重新更新head和tail
                tail -= head;
                head = 0;
            }

            items[tail] = item;
            ++tail;
            return true;
        }

        // 出队
        public String dequeue() {
            // 如果head == tail 表示队列为空
            if (head == tail) return null;
            // 为了让其他语言的同学看的更加明确，把--操作放到单独一行来写了
            String ret = items[head];
            ++head;
            return ret;
        }
    }


    /**
     * 数组循环队列
     */
    public class CircularQueue {
        // 数组：items，数组大小：n
        private String[] items;
        private int n = 0;
        // head表示队头下标，tail表示队尾下标
        private int head = 0;
        private int tail = 0;

        // 申请一个大小为capacity的数组
        public CircularQueue(int capacity) {
            items = new String[capacity];
            n = capacity;
        }

        // 入队
        public boolean enqueue(String item) {
            // 队列满了
            if ((tail + 1) % n == head) return false;
            items[tail] = item;
            tail = (tail + 1) % n;
            return true;
        }

        // 出队
        public String dequeue() {
            // 如果head == tail 表示队列为空
            if (head == tail) return null;
            String ret = items[head];
            head = (head + 1) % n;
            return ret;
        }
    }

    /**
     * 单向链表队列
     */
    public static class LinkedQueue<T> {

        Node<T> head;

        public boolean enqueue(T val) {
            if (head == null) {
                head = new Node<>(val);
                return true;
            }
            head.next = new Node<>(val);
            return true;
        }

        public T dequeue() {
            if (head == null) {
                return null;
            }
            T val = head.val;
            head = head.next;
            return val;
        }

        public class Node<T> {
            T val;
            Node<T> next;

            public Node(T val) {
                this.val = val;
            }
        }

    }

    /**
     * 跳表 - 可二分查找的多层索引有序链表，范围查找效率比红黑树高，插入，删除，查找时间复杂度都是O(logn)，空间复杂度O(n)
     */
    public class SkipList<T extends Comparable<? super T>> {
        private int maxLevel;
        private SkipListNode<T>[] root;
        private int[] powers;
        private Random rd = new Random();

        SkipList() {
            this(4);
        }

        SkipList(int i) {
            maxLevel = i;
            root = new SkipListNode[maxLevel];
            powers = new int[maxLevel];
            for (int j = 0; j < maxLevel; j++)
                root[j] = null;
            choosePowers();
        }

        public boolean isEmpty() {
            return root[0] == null;
        }

        public void choosePowers() {
            powers[maxLevel - 1] = (2 << (maxLevel - 1)) - 1;    // 2^maxLevel - 1
            for (int i = maxLevel - 2, j = 0; i >= 0; i--, j++)
                powers[i] = powers[i + 1] - (2 << j);           // 2^(j+1)
        }

        public int chooseLevel() {
            int i, r = Math.abs(rd.nextInt()) % powers[maxLevel - 1] + 1;
            for (i = 1; i < maxLevel; i++)
                if (r < powers[i])
                    return i - 1; // return a level < the highest level;
            return i - 1;         // return the highest level;
        }

        // make sure (with isEmpty()) that search() is called for a nonempty list;
        public T search(T key) {
            int lvl;
            SkipListNode<T> prev, curr;            // find the highest nonnull
            for (lvl = maxLevel - 1; lvl >= 0 && root[lvl] == null; lvl--) ; // level;
            prev = curr = root[lvl];
            while (true) {
                if (key.equals(curr.key))          // success if equal;
                    return curr.key;
                else if (key.compareTo(curr.key) < 0) { // if smaller, go down,
                    if (lvl == 0)                 // if possible
                        return null;
                    else if (curr == root[lvl])   // by one level
                        curr = root[--lvl];      // starting from the
                    else curr = prev.next[--lvl]; // predecessor which
                }                                  // can be the root;
                else {                             // if greater,
                    prev = curr;                  // go to the next
                    if (curr.next[lvl] != null)   // non-null node
                        curr = curr.next[lvl];   // on the same level
                    else {                        // or to a list on a lower level;
                        for (lvl--; lvl >= 0 && curr.next[lvl] == null; lvl--) ;
                        if (lvl >= 0)
                            curr = curr.next[lvl];
                        else return null;
                    }
                }
            }
        }

        public void insert(T key) {
            SkipListNode<T>[] curr = new SkipListNode[maxLevel];
            SkipListNode<T>[] prev = new SkipListNode[maxLevel];
            SkipListNode<T> newNode;
            int lvl, i;
            curr[maxLevel - 1] = root[maxLevel - 1];
            prev[maxLevel - 1] = null;
            for (lvl = maxLevel - 1; lvl >= 0; lvl--) {
                while (curr[lvl] != null && curr[lvl].key.compareTo(key) < 0) {
                    prev[lvl] = curr[lvl];           // go to the next
                    curr[lvl] = curr[lvl].next[lvl]; // if smaller;
                }
                if (curr[lvl] != null && key.equals(curr[lvl].key)) // don't
                    return;                          // include duplicates;
                if (lvl > 0)                         // go one level down
                    if (prev[lvl] == null) {         // if not the lowest
                        curr[lvl - 1] = root[lvl - 1]; // level, using a link
                        prev[lvl - 1] = null;        // either from the root
                    } else {                           // or from the predecessor;
                        curr[lvl - 1] = prev[lvl].next[lvl - 1];
                        prev[lvl - 1] = prev[lvl];
                    }
            }
            lvl = chooseLevel();                // generate randomly level
            newNode = new SkipListNode<T>(key, lvl + 1); // for newNode;
            for (i = 0; i <= lvl; i++) {        // initialize next fields of
                newNode.next[i] = curr[i];      // newNode and reset to newNode
                if (prev[i] == null)            // either fields of the root
                    root[i] = newNode;         // or next fields of newNode's
                else prev[i].next[i] = newNode; // predecessors;
            }
        }

        private class SkipListNode<T> {
            T key;

            SkipListNode[] next;


            public SkipListNode(T key, int i) {
            }
        }
    }


}